1. Field of the Invention
The present invention concerns computer-memory allocators and in particular mechanisms that they employ for splitting memory blocks.
2. Background Information
Some of the instructions that a processor reads from its memory direct it to read data stored in other memory locations. The program as loaded often specifies the locations in which the data are to be stored: memory is allocated statically. But many programs generate large quantities of intermediate results that require only temporary storage. To use memory efficiently, memory should not be allocated to such results unless and until they are actually produced: it should be allocated dynamically. And, once the program no longer needs the data for which space was thus allocated, the program should be allowed to reuse that memory space.
For this reason, most large programs employ a xe2x80x9cheapxe2x80x9d of dynamically allocable memory. As the program proceeds, various previously free memory blocks within the heap contain needed data, while other memory blocks become free for reuse because they contain data that are no longer needed. To keep track, the computer system usually maintains an inventory of locations and sizes of xe2x80x9cfreexe2x80x9d memory blocks, i.e., of memory blocks that can receive new results.
Now, computer programs typically deal with data as various-sized xe2x80x9cobjects,xe2x80x9d each of which usually has all of its data stored in contiguous memory locations. So a block of (contiguous) memory locations must be found when the time comes to allocate memory dynamically to an object. An allocator is the system component that handles the task of keeping track of such free memory blocks and determining which of the free memory blocks are to be used to store new data.
Allocators occur at various levels in the software hierarchy. An operating system itself generates data for which it must dynamically allocate memory, so one of an operating system""s tasks is to act as an allocator for that purpose. The operating system typically also serves as an allocator in response to various system calls made by applications programs. The C library function malloc( ), for instance, is a system call that an application uses to ask the system to allocate memory to the application. The free( ) library function conversely tells the system that the calling process no longer needs the data contained by the memory block that the call identifies.
Additionally, some applications that have called upon the operating system to allocate them memory will in turn act as allocators in xe2x80x9csub-allocatingxe2x80x9d that memory. An example of such an application is the Java Virtual Machine (xe2x80x9cJVMxe2x80x9d). (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Such an application calls upon the operating system to allocate it memory for its private heap, which it sub-allocates to objects created by the virtual-machine-language programs that it executes. The input to the JVM is one or more xe2x80x9cclass files,xe2x80x9d which include virtual-machine programs, i.e., sequences of the virtual machine""s instructions. Included in the virtual machine""s instruction set are instructions for allocating new objects, and the virtual machine can so operate as to allocate object memory by removing blocks from the free-block inventory. The JVM not only executes the class file""s explicit instructions but also performs automatic xe2x80x9cgarbage collectionxe2x80x9d: it identifies objects that the virtual-machine program will no longer use. The JVM may add such objects"" memory space to the free-block inventory after they are thus identified.
Independently of the software-hierarchy level at which an allocator operates, one function that it must perform is xe2x80x9csplitting.xe2x80x9d When a program frees a memory block of a relatively large size, the allocator may initially place it in its free-block inventory as a single block. Or, when the program frees several contiguous small memory blocks, the allocator may xe2x80x9ccoalescexe2x80x9d those entries into a single large block. (Workers in this field treat coalesce as a transitive verb.) In either case, the allocator may subsequently split that block into smaller blocks if a program thereafter requests allocation of a smaller block and no block of the requested size is available.
Performing such splitting is desirable because it conserves memory resources; allocating a large block in response to a request for a small one wastes memory space. But it can also detract from program performance; in a program that frequently allocates memory dynamically, the cost of splitting can become significant.
We have developed an approach to splitting that can reduce splitting cost. In accordance with the invention, we derive a demand indicator for each of a plurality of memory-block size ranges. Preferably, this is done by monitoring at run time the allocations of memory blocks whose sizes fall within the respective ranges, although demand derivation can instead be performed by static (compile-time) analysis or by profiling a previous execution of the program. One way to use the demand indicators is to compare the demand signified by the demand indicator for a given block size with the supply of blocks of that size. Typically, if the supply of blocks of a given size exceeds a demand projected for blocks of that size, then blocks of that size will tend to be selected for splitting, whereas blocks whose sizes not in adequate supply will tend not to be selected. This tends to reduce the likelihood that splitting performed at one time will necessitate further splitting or coalescing at a later time.